ABC269 D - Do use hexagon grid

https://atcoder.jp/contests/abc269/tasks/abc269_d

提出

code: python

n = int(input())

xy = list(map(int, input().split())) for _ in range(n)

xy = sorted(xy, reverse=True, key=lambda x: x1)

visited = []

def dfs(x_y):

visited.append(x_y)

x = x_y0

y = x_y1

to = -1, -1], -1, 0, 0, -1, 0, 1, 1, 0, [1, 1

for t in to:

if [x+t0, y+t1] not in xy:

continue

if [x+t0, y+t1] in visited:

continue

dfs([x+t0, y+t1])

visited.append("#")

for x_y in xy:

if x_y in visited:

continue

dfs(x_y)

ans = 0

for i in range(len(visited)-1):

if visitedi != "#" and visitedi+1 == "#":

ans += 1

print(ans)

解答

code: python

n = int(input())

xy = list(map(int, input().split())) for _ in range(n)

offset = 1000

index_range = offset * 2 + 1

field = [0 for _ in range(index_range) for _ in range(index_range)]

for x, y in xy:

fieldx + offsety + offset = 1

to_x = -1, -1, 0, 0, 1, 1

to_y = -1, 0, -1, 1, 0, 1

def dfs(x, y):

fieldxy = 0

for i in range(6):

if 0 <= x + to_xi and x + to_xi < index_range and \

0 <= y + to_yi and y + to_yi < index_range and \

field[to_xi + x][to_yi + y] == 1:

dfs(to_xi + x, to_yi + y)

result = 0

for x in range(index_range):

for y in range(index_range):

if fieldxy == 1:

dfs(x, y)

result += 1

print(result)

テーマ

#dfs

メモ

ABC269 D問題（Do use hexagon grid）を解く

提出

code: python

n = int(input())

xy = list(map(int, input().split())) for _ in range(n)

visited = []

# 1000 * 1000

def dfs(nowx, nowy):

toi = -1, 1, 0, 0, 1, 1

toj = -1, 0, -1, 1, 0, 1

for t in range(6):

nextx = nowx + toit

nexty = nowy + tojt

if nextx, nexty in xy and not nextx, nexty in visited:

visited.append(nextx, nexty)

dfs(nextx, nexty)

print("yes")

for x in range(1000):

for y in range(1000):

if x, y in xy:

dfs(x, y)

print("foo")